package com.salim.leetcode.$39;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        loop(new ArrayList<>(),candidates,0,0,target,result);
        return result;
    }

    public void loop(List<Integer> currentList,int[] candidates,int left,int sum,int target,List<List<Integer>> result){
        for(int i=left;i<candidates.length;i++){
            //由于数字不相同 可以直接返回
            if(sum+candidates[i] == target){
                currentList.add(candidates[i]);
                result.add(currentList);
                break;
            }
            if(sum+candidates[i]>target){
                break;
            }
            if(sum+candidates[i]<target){
                List<Integer> next = new ArrayList<>(currentList);
                next.add(candidates[i]);
                loop(next, candidates,i,sum+candidates[i],target,result);
            }
        }
    }
}
